package com.sheng.leetcode.year2025.month10.day07;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2025/10/14
 * <p>
 * 1488. 避免洪水泛滥<p>
 * <p>
 * 你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的，那么它就会装满水。<p>
 * 如果第 n 个湖泊下雨前是 满的 ，这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。<p>
 * 给你一个整数数组 rains ，其中：<p>
 * rains[i] > 0 表示第 i 天时，第 rains[i] 个湖泊会下雨。<p>
 * rains[i] == 0 表示第 i 天没有湖泊会下雨，你可以选择 一个 湖泊并 抽干 这个湖泊的水。<p>
 * 请返回一个数组 ans ，满足：<p>
 * ans.length == rains.length<p>
 * 如果 rains[i] > 0 ，那么ans[i] == -1 。<p>
 * 如果 rains[i] == 0 ，ans[i] 是你第 i 天选择抽干的湖泊。<p>
 * 如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。<p>
 * 请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。<p>
 * <p>
 * 示例 1：<p>
 * 输入：rains = [1,2,3,4]<p>
 * 输出：[-1,-1,-1,-1]<p>
 * 解释：第一天后，装满水的湖泊包括 [1]<p>
 * 第二天后，装满水的湖泊包括 [1,2]<p>
 * 第三天后，装满水的湖泊包括 [1,2,3]<p>
 * 第四天后，装满水的湖泊包括 [1,2,3,4]<p>
 * 没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。<p>
 * <p>
 * 示例 2：<p>
 * 输入：rains = [1,2,0,0,2,1]<p>
 * 输出：[-1,-1,2,1,-1,-1]<p>
 * 解释：第一天后，装满水的湖泊包括 [1]<p>
 * 第二天后，装满水的湖泊包括 [1,2]<p>
 * 第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]<p>
 * 第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。<p>
 * 第五天后，装满水的湖泊包括 [2]。<p>
 * 第六天后，装满水的湖泊包括 [1,2]。<p>
 * 可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。<p>
 * <p>
 * 示例 3：<p>
 * 输入：rains = [1,2,0,1,2]<p>
 * 输出：[]<p>
 * 解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。<p>
 * 但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。<p>
 * <p>
 * 提示：<p>
 * 1 <= rains.length <= 10^5<p>
 * 0 <= rains[i] <= 10^9<p>
 */
public class LeetCode1488 {

    @Test
    public void test01() {
//        int[] rains = {1, 2, 3, 4};
//        int[] rains = {1, 2, 0, 0, 2, 1};
//        int[] rains = {1, 2, 0, 1, 2};
//        int[] rains = {0, 1, 1};
        int[] rains = {1, 0, 2, 0, 2, 1};
        System.out.println(Arrays.toString(new Solution().avoidFlood(rains)));
    }
}

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] ans = new int[n];
        // 只有 rains == 0 时，才能进行抽水，即两个相同的元素之间必须得有一个或多个零，否则就会发洪水
        // 首先判断是否能阻止发洪水，
        Map<Integer, Integer> integers = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        int count = 0, w = 0;
        int index;
        for (int i = 0; i < n; i++) {
            index = -1;
            if (rains[i] == 0) {
                list.add(i);
                count++;
            } else {
                if (integers.containsKey(rains[i])) {
                    w++;
                    if (w > count) {
                        return new int[]{};
                    }
                    for (int i1 = 0; i1 < list.size(); i1++) {
                        if (list.get(i1) > integers.get(rains[i])) {
                            // 在满足条件不下雨的那一天把这个坑位给填满
                            ans[list.get(i1)] = rains[i];
                            index = i1;
                            break;
                        }
                    }
                    if (index != -1) {
                        list.remove(index);
                    } else {
                        return new int[]{};
                    }
                }
                // 将下雨的位置更新到集合中
                integers.put(rains[i], i);
                ans[i] = -1;
            }
        }
        for (Integer i : list) {
            ans[i] = 1;
        }
        return ans;
    }
}
